Split array into Fibonacci sequence [Brute Force]

Time: O(N^3); Space: O(N); medium

Given a string S of digits, such as S = ‘123456579’, we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that: 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: S = ‘123456579’

Output: [123,456,579]

Example 2:

Input: S = ‘11235813’

Output: [1,1,2,3,5,8,13]

Example 3:

Input: S = ‘112358130’

Output: []

Explanation:

  • The task is impossible.

Example 4:

Input: S = ‘0123’

Output: []

Explanation:

  • Leading zeroes are not allowed

Example 5:

Input: S = ‘1101111’

Output: [110, 1, 111]

Explanation:

  • The output [11, 0, 11, 11] would also be accepted.

Constraints:

  • 1 <= len(S) <= 200

  • S contains only digits.

1. Brute Force

Intuition

The first two elements of the array uniquely determine the rest of the sequence.

Algorithm

For each of the first two elements, assuming they have no leading zero, let’s iterate through the rest of the string. At each stage, we expect a number less than or equal to 2^31 - 1 that starts with the sum of the two previous numbers.

[6]:

class Solution1(object):
    def splitIntoFibonacci(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        for i in range(min(10, len(S))):
            x = S[:i + 1]
            if x != '0' and x.startswith('0'):
                break
            a = int(x)
            for j in range(i + 1, min(i + 10, len(S))):
                y = S[i + 1: j + 1]
                if y != '0' and y.startswith('0'):
                    break
                b = int(y)
                fib = [a, b]
                k = j + 1
                while k < len(S):
                    nxt = fib[-1] + fib[-2]
                    nxtS = str(nxt)
                    if nxt <= 2**31 - 1 and S[k:].startswith(nxtS):
                        k += len(nxtS)
                        fib.append(nxt)
                    else:
                        break
                else:
                    if len(fib) >= 3:
                        return fib
        return []

[7]:

s = Solution1()
S = '123456579'
assert s.splitIntoFibonacci(S) == [123,456,579]
S = '11235813'
assert s.splitIntoFibonacci(S) == [1,1,2,3,5,8,13]
S = '112358130'
assert s.splitIntoFibonacci(S) ==  []
S = '0123'
assert s.splitIntoFibonacci(S) == []
S = '1101111'
assert s.splitIntoFibonacci(S) == [110, 1, 111] or [11, 0, 11, 11]

[8]:

class Solution2(object):
    def splitIntoFibonacci(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        def startsWith(S, k, x):
            y = 0
            for i in range(k, len(S)):
                y = 10* y + int(S[i])
                if y == x:
                    return i - k + 1
                elif y > x:
                    break
            return 0

        MAX_INT = 2**31-1
        a = 0
        for i in range(len(S)-2):
            a = 10 * a + int(S[i])
            b = 0
            for j in range(i + 1, len(S) - 1):
                b = 10 * b + int(S[j])
                fib = [a, b]
                k = j + 1
                while k < len(S):
                    if fib[-2] > MAX_INT-fib[-1]:
                        break
                    c = fib[-2] + fib[-1]
                    length = startsWith(S, k, c)
                    if length == 0:
                        break
                    fib.append(c)
                    k += length
                else:
                    return fib
                if b == 0:
                    break
            if a == 0:
                break
        return []

[9]:

s = Solution2()
S = '123456579'
assert s.splitIntoFibonacci(S) == [123,456,579]
S = '11235813'
assert s.splitIntoFibonacci(S) == [1,1,2,3,5,8,13]
S = '112358130'
assert s.splitIntoFibonacci(S) ==  []
S = '0123'
assert s.splitIntoFibonacci(S) == []
S = '1101111'
assert s.splitIntoFibonacci(S) == [110, 1, 111] or [11, 0, 11, 11]